Many pattern matching problems can be formulated in terms of finding similar distributions in two point sets. For instance, in star tracking a library template is matched to the star detections on a sensor's focal plane to establish spacecraft attitude. In various other pattern matching applications where such discrete points are not directly obtained, feature points of the input patterns are first obtained using well-known prior art techniques. One example of which is fingerprint identification, where minutia points are derived from a latent fingerprint. These minutia points are then used to attempt a match of the latent fingerprint with a file print.
Not all comparisons are performed against a stored template. Numerous applications require that a match be performed between patterns obtained by separate system sensors thereby increasing problems associated with measurement errors. By way of example, in tracking and surveillance applications, point-set matching, or correlation, is critical to determining whether multiple sensors are seeing the same objects. A common technique for correlating two point sets is least-cost assignment, such as the Munkres or Jonker-Vollgenant-Castenanon algorithm. With this approach, the cost of associating pairs of points, one from each set, is either the Euclidean or Mahalanobis distance (χ2-statistic). Thus, the best correlation solution is one that minimizes the sum of the distances between associated pairs.
This approach works well in many cases and can be applied if the sets consist of unequal numbers of points. However, there are serious limitations. It is necessary to first estimate the bias or offset between the two sets, substantially increasing the algorithm's complexity—especially if the bias has a rotation component. For example, aligning reconnaissance photos usually requires translations and rotation, and possibly scaling. Typically, such prior art algorithms also force each point in the smaller set to correlate with some point in the larger set. These forced associations may not be valid. For instance, there is no guarantee that two sensors surveying the same region will detect the same objects. Another limitation with many correlation algorithms is their limited ability to handle errors in estimating an object's location. As a consequence correlated points may not align exactly. Finally, multiple alignments may exist, indicating a degree of ambiguity that could cast suspicion on the validity of any single solution. In the extreme, any two points could be correlated if the allowable error is large enough. Further, since a typical least-cost assignment algorithm will stop with the first solution it finds, the user may never suspect the poor quality of the correlation. This is particularly critical in coordinated surveillance systems where tracks from multiple sensors must be associated with a high degree of reliability.
The Distance-Sort algorithm of the present invention circumvents these limitations. With the present invention bias estimation is a consequence of the correlation solution and not a necessary first step. The present invention's Distance-Sort is robust to missing data and sensor errors, finding all the possible alignments given the allowable error.